package graph_algorithms;

/**
 * author :  apurv verma
 * email  :  dapurv5@gmail.com
 */

import java.awt.Dimension;
import java.util.Stack;
import sorting_algorithms.MergeSort;

public class KruksalsAlgorithm {
	private Graph g;
	private double l[];
	private boolean b[][]; //THE ARRAY OF EDGES WHICH HAVE BEEN SELECTED IN THE SpanTree.
	
	public double lenSpanTree;
	public Dimension spanTree[];
	
	public KruksalsAlgorithm(Graph g){
		lenSpanTree=0;
		this.g=g;
		b=new boolean[g.n][g.n];
	}
	
	public void shortestSpanningTree(){
		//STORE THE NUMBER OF EDGES IN n.
		int n=0;
		for(int i=0;i<g.n;i++){
			for(int j=0;j<=i;j++){
				if (g.G[i][j]){
					n++;
				}
			}
		}
		//STORE THE EDGE LENGTHS IN l[] AND THE VERTICES CONNECTING THEM IN I[], J[].
		l=new double[n];
		int I[]=new int[n];
		int J[]=new int[n];
		int k=0;
		for(int i=0;i<g.n;i++){
			for(int j=0;j<=i;j++){
				if (g.G[i][j]){
					l[k]=g.D[i][j];
					I[k]=i;
					J[k]=j;
					k++;
				}
			}
		}
		
		MergeSort.mergesortAccordingly(l,I,J, 0, n-1);
		
		int x;int y;int pos=0;
		for(int i=0;i<l.length;i++){
			x=I[i];
			y=J[i];
			
			if ( formACycle(-1,x,y) ){
			}
			else{
				lenSpanTree=lenSpanTree+g.D[x][y];
				b[x][y]=true;
				b[y][x]=true;
				I[pos]=x;
				J[pos]=y;
				pos++;
			}
		}
		spanTree=new Dimension[pos];
		
		//System.out.println("The shortest Spanning tree by Kruksals Greedy Algorithm is: \n");
		for(int i=0;i<pos;i++){
			//System.out.print(I[i]+","+J[i]+"->");
			spanTree[i]=new Dimension(I[i],J[i]);
		}
		//System.out.println("And the length of the spanning tree is ="+lenSpanTree);
		
	}
	
	//formACycle(i,j) IS EQUIVALENT TO ASKING WHETHER THERE EXISTS A PATH BETWEEN i AND j IN s.s.t. SUBGRAPH THAT HAS BEEN SELECTED.
	private boolean formACycle(int prev,int i, int j){
		boolean result=false;
		Stack<Integer> s=new Stack<Integer>();
		for(int it=0;it<g.n;it++){
			if(b[i][it] && it!=prev){
				s.add(it);
			}
		}
		
		for(int it=0;it<s.size();it++){
			if((Integer)s.elementAt(it)==j){
				return true;
			}
		}
		while(!s.empty()){
			result=formACycle(i,(Integer)s.pop(),j);
		}
		return result;
	}
}
